#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e5 + 5;
const int MOD = 2333;
ll n, m;
ll c[3005][3005];
ll sum[3005][3005];
void init() {
  rep(i, 0, MOD) c[i][0] = 1;
  rep(i, 1, MOD) rep(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  rep(i, 0, MOD) {
    sum[i][0] = 1;
    rep(j, 1, MOD) sum[i][j] = (sum[i][j - 1] + c[i][j]) % MOD;
  }
}
ll cmb(ll n, ll m) { return c[n][m]; }
ll lucas(ll n, ll m) {
  if (m > n) return 0;
  if (m == 0 || m == n) return 1;
  return lucas(n / MOD, m / MOD) * cmb(n % MOD, m % MOD) % MOD;
}
ll cmb2(ll n, ll m) { return sum[n][m]; }
ll lucas2(ll n, ll m) {
  ll s = (m + 1) / MOD * MOD - 1;
  ll res = 0;
  if (s >= 0) res = lucas2(n / MOD, s / MOD) * cmb2(n % MOD, MOD - 1) % MOD;
  if (s + 1 <= m) {
    ll x = lucas(n / MOD, (s + 1) / MOD);
    ll y = cmb2(n % MOD, m % MOD);
    res = (res + x * y % MOD) % MOD;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init();
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> m;
    cout << lucas2(n, m) << endl;
  }
  return 0;
}